Embodiments of the invention relate to the field of network synchronization, and in particular to the field of decentralized network synchronization. Embodiments of the invention concern the frequency synchronization in such networks.
In recent years many everyday items have gained wireless capabilities so that wireless communication among electronic devices becomes more and more popular and common. One approach for such wireless communication among electronic devices is to organize the devices in an ad hoc network or in a peer-to-peer network, i.e. a decentralized network.
FIG. 1 shows a schematic representation of an ad hoc network formed by a plurality of wireless devices MS that directly communicate with each other as indicated by the arrows. The ad hoc network is set up in such a way that some of the wireless devices MS directly communicate with each other while the communication between distant wireless devices MS like wireless devices 100 and 102 occurs via intermediate wireless devices. The wireless devices may be mobile stations or PDAs having a wireless communication capability or any other electronic device allowing for a wireless communication with its environment. The wireless devices shown in FIG. 1 are also referred to as the “nodes” of the wireless network.
In such a network synchronization of the communication among the respective devices is required. Synchronization schemes known in the art assume that nodes form a fully meshed network, which can be true in a wireless network. However, in general this assumption does not hold for two reasons. First, when considering that nodes are spread over a large area or have low transmission power, a node can only communicate with nodes which are within its transmission range, i.e. with neighboring nodes, as mentioned above with regard to FIG. 1. Further, for communications between nodes in a peer-to-peer fashion, a fully meshed network requires nodes to transmit with very high power, which may not always be possible when nodes are very far apart and also causes high interference, so that that it is preferable to lower transmission power. Thus, in many cases the topology of a wireless network as shown in FIG. 1 is not a fully meshed one. Two devices in the network, like the electronic devices 100 and 102 are not necessarily within transmission range, but they communicate by using neighboring nodes, thus forming a multi-hop network.
Prior art approaches suggest a time synchronization in such a network in a distributed fashion. Time synchronization is defined as aligning local time units in order to define a common slot structure among all nodes. Basically, the slot synchronization among the respective wireless devices MS is advantageous as it enables synchronous multicast services and coordinated multipoint (CoMP) schemes. Further, the design of interference management algorithms may be simplified because synchronization is a basic form of coordination.
The network shown in FIG. 1 can be considered a network of femtocells and each femtocell is typically equipped with a cheap local oscillator having a poor clock quality. A clock signal from a macrocell may be difficult to obtain indoors, so that, in accordance with known approaches, the synchronization is performed among the femtocells. However, clock generators and the clocks provided by them are inherently imperfect, i.e. there is no clock that can maintain a perfect track of time and frequency over time. Clock generators and their characteristics thus change over time, however, their characteristics also fluctuate when environmental conditions vary, for example, the temperature. This leads to clock jitter in time and in frequency, so that clocks need to be periodically re-synchronized. This problem is even more severe in the above described femto networks using low-quality clock generators the characteristics of which will change more rapidly than the characteristics of high-quality clock generators. However, it has to be mentioned even in case of high-quality clock generators that there is no perfect clock.
In the art various forms of network synchronizations have been proposed, which typically rely on a master-slave type of architecture. A master clock dictates its timing and frequency to the slave clock. This solution requires a very high clock quality for the master, however, is prone to single points of failure because the slave clock completely depends on the master clock.
An alternative known approach is to perform synchronization in a decentralized manner. In such a scenario each node updates its clock based on the detected neighboring clock and in return it influences also its neighbors. Therefore, in such approaches local update rules need to be designed that lead to the synchronization of the network. Decentralized network synchronization solutions have been proposed. Based on the theory of pulse-covered oscillators, a solution described by Tyrrell, A.; Auer, G. and Bettstetter, C. an “Emergent Slot Synchronization in Wireless Networks”, IEEE Transactions on Mobile Computing, 2010, vol. 9, pp. 719-732, and also described in EP 1 852 998 A1 focuses on time synchronization. This known approach applies a biologically inspired technique to perform a decentralized slot synchronization in wireless networks. In accordance with this known approach each node maintains a phase function φi(t), which varies at a given frequency φi(t)/dt=1/T. The phase of the clock is updated when a packet is received, based on the detected timing of packets {circumflex over (τ)}ij. However, in accordance with this approach only time synchronization is provided so that the also existing frequency offsets of the oscillators used are not addressed.
Another known solution is described by Ebner, A.; Rohling, H.; Halfmann, R. and Lott, M. “Synchronization in ad hoc networks based on UTRA TTD” Proceedings IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC), 2002. This approach is targeted at UMTS vehicular communications, however, it requires to first perform a time synchronization before performing the task of frequency synchronization. More specifically, in a first step a coarse or one-shot time synchronization is performed using GPS (GPS=Global Positioning System). Following this, a fine time synchronization is performed. Only once these two steps for time synchronization are completed a coarse frequency synchronization followed by a fine frequency synchronization is carried out. However, this approach requires to first perform the time synchronization before performing the frequency synchronization, that is without the first step this approach cannot cope with any initial timing misalignment. In addition, time synchronization is performed using GPS which is not available indoor for femtocells. Further, using the GPS approach already guarantees a time synchronization precision of microseconds that can also be used for frequency synchronization as GPS clocks are very accurate, as is described by Lewandowski, W.; Petit, G. and Thomas, C. “Precision and accuracy of GPS time transfer” IEEE Transactions on Instrumentation and Measurement, 1993, vol. 42, pp. 474-479.
With regard to FIG. 2, the problems of a missing frequency synchronization in decentralized networks as is, for example, shown in FIG. 1, will be explained in further detail. FIG. 2 shows, as an example, the transmission slots of three nodes, namely node 1, node 2 and node 3 of a network as is shown in FIG. 1. Naturally, such a network comprises either more or less nodes and the diagram of FIG. 2 is a schematic diagram for discussing the problems of a missing frequency synchronization in such networks. In the nodes the start and duration of a slot are given by the slot clock φi(t). Upon receiving a synchronization word the start time of a slot at which φi(t)=0 is set to the same point of time in all nodes, and the duration of a slot within a node is given by the clock generator frequency that is defined as
      f    i    =                    ⅆ                              ϕ            i                    ⁡                      (            t            )                                      ⅆ        t              =                  1                  T          i                    .      In FIG. 2, at time t0 a synchronization word S is received at each of nodes 1, 2 and 3. On the basis of the synchronization word or the synchronization signal S, the start of a slot for each node is readjusted. The synchronization word S is received periodically, for example, in accordance with one known standard after five slots for readjusting the start of the slots again. Thus, time synchronization results in a common starting point in time, namely point t0 at which in each node the first slot starts. As mentioned above, the duration of the slots is given by the frequency of the local clock generator. As can be seen, nodes 1, 2 and 3 have a duration for each slot of T1, T2 and T3, respectively. However, the frequencies of the respective clock generators are not synchronized, i.e. each clock generator operates on its own frequency, so that, as can be seen from FIG. 2, node 1 has a first slot duration T1 that is longer than the slot duration T2 of node 2, however, shorter than the slot duration T3 of node 3. Thus, the slot of node 2 ends first at time T1. The slot of node 1 ends second at time T2. The longest slot is the one of node 3 that ends last at time T3. Thus, following the receipt of the time synchronization S after the first slot, the start times of the following slots are no longer aligned, rather, as can be seen they spread over time, i.e. there is an offset of t2-t1 between the start of the second slot of node 2 and the start of the second slot of node 1. Also, there is an offset, of t3-t1 between the start of a second slot of node 2 and a second slot of node 3. The maximum offset between the shortest slot, the slot of node 2 and the longest slot, the slot of node 3 is indicated in FIG. 2 as O1. Due to this offset between the respective nodes, the starting times of the subsequent slots are no longer aligned, so that without frequency synchronization the spread in slot starts increases over time. This can be seen from FIG. 2 showing the offset between the shortest slot, the slot of node 2 and the longest slot, the slot of node 3, after five slots. This is indicated in FIG. 2 at O2. As can be seen, this offset increases dramatically. Actually, in this scenario node 2 already processed five slots while node 3 only processed four slots.
Thus, in case the nodes are not frequency synchronized, the slot length varies, that is the start of subsequent slots diverges over time.